package com.yuan.algorithms.面试题;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 请实现一个LRU缓存
 * 通过继承LinkedHashMap可以很好的实现一个缓存，只要在new LinkedHashMap传入accessOrder参数为true即可
 * 同时重写removeEldestEntry方法能够实现数据新增的时候判断缓存容量是否满了，这个方法由put和putAll在映射中插入一个新条目后调用。
 * 它为实现者提供了每次添加新条目时删除最老条目的机会。
 * @author YouYuan
 * @date 2022/3/25 10:19
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    /**
     * 缓存容量
     */
    private int capacity;


    public LRUCache(int capacity) {
        //调用LinkedHashMap构造方法开启访问顺序排序
        super(16, 0.75f, true);
        //指定的缓存最大容量
        this.capacity = capacity;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 复写核心方法，完成LRU删除逻辑
     * 如果该映射应该删除其最老的条目，则返回true。
     * 这个方法由put和putAll在映射中插入一个新条目后调用。
     * 它为实现者提供了每次添加新条目时删除最老条目的机会。
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        if (size() > capacity) {
            System.out.println("LRU remove:" + eldest.getKey() + "=" + eldest.getValue());
        }
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache<>(6);
        lruCache.put("a", 1);
        lruCache.put("b", 2);
        lruCache.put("c", 3);
        lruCache.put("d", 4);
        lruCache.put("e", 5);
        lruCache.put("f", 6);
        lruCache.get("a");
        lruCache.get("c");
        lruCache.put("g", 7);
        lruCache.put("h", 8);
        // 因为使用了a、c，在缓存超出容量之后删除的是最早未使用的数据，所以b、d被清除了
        lruCache.forEach((k, v) -> System.out.println(k + "=" + v));
    }
}
